//给你一个字符串 s，找到 s 中最长的 回文 子串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
//
// Related Topics 双指针 字符串 动态规划 👍 7430 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function longestPalindrome(s: string): string {
    //? dp[i][j] [i,j]区间的最长回文子串
    //? 当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

    //? 当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

    //? 情况一：下标i与j相同，同一个字符例如a，当然是回文子串
    //? 情况二：下标i与j相差为1，例如aa，也是回文子串
    //? 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，
    //? 那么aba的区间就是i+1与j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
    const length: number = s.length;
    const dp: boolean[][] = new Array(length).fill(0)
        .map(_ => new Array(length).fill(false));
    let maxlenth: number = 0;
    let left : number = 0
    // 自下而上，自左向右遍历
    for (let i = length - 1; i >= 0; i--) {
        for (let j = i; j < length; j++) {
            if (
                //? 下标相同必然满足j - i <=1 （情况1）
                //? j - i <=1 （情况2）
                s[i] === s[j] &&
                //? 不满足j - i <=1 即判断dp[i + 1][j - 1] === true（情况3）
                (j - i <= 1 || dp[i + 1][j - 1] === true)  //? 三种情况一并概况为true 其他情况不动，因为初始化为false
            ) {
                dp[i][j] = true;
                if(dp[i][j] && j - i + 1 > maxlenth) {
                    maxlenth = j - i + 1; // 回文串长度
                    left = i; // 起始位置
                }
            }
        }
    }
    return s.substr(left, maxlenth);
};
//leetcode submit region end(Prohibit modification and deletion)
